<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8" />
  <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  <title>快速排序</title>
</head>

<body>

</body>
<script>
  // 快速排序:
  // 首先设置一个分界值，通过该分界值将数据分割成两部分。
  // 将大于或等于分界值的数据集中到右边，小于分界值的数据集中到左边。
  // 然后，左边和右边的数据可以看成两组不同的部分，重复上述1和2步骤
  // 当左右两部分都有序时，整个数据就完成了排序


  function quick(arr) {
    // 4. 结束递归（当 arr 小于等于一项，就不用处理了）
    if (arr.length <= 1) {
      return arr
    }

    // 1. 找到数组的中间项,在原有数组中把它移除
    let middleIndex = Math.floor(arr.length / 2)
    let middleValue = arr.splice(middleIndex, 1)[0]

    // 2. 准备左右两个数组，循环剩下数组的每一项，比当前项小的放在左边数组，反之放在右边数组
    let arrLeft = [], arrRight = []
    for (let i = 0; i < arr.length; i++) {
      let item = arr[i]
      item < middleValue ? arrLeft.push(item) : arrRight.push(item)
    }

    // 3. 递归方式让左右两边的数组持续这样处理，直到左右两边都排好序为止（最后让左边+中间项+右边拼接成为最后的结果）
    return quick(arrLeft).concat(middleValue, quick(arrRight))
  }
  let arr = [12, 45, 9, 10, 50, 100, 3]

  arr = quick(arr)
  console.log(arr);
</script>

</html>